﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class LRUCache1//自己使用数组+栈的思想实现，也是LRU的原理
{

    private int _capacity;

    private int[] caches = new int[10000] ;//把这个换成字典可以优化
    
    private int[] stack;//这个栈，用来存key
    //使用一个指针指向栈顶，新使用的入栈
    int top = 0;
    //以 正整数 作为容量 capacity 初始化 LRU 缓存
    public LRUCache1(int capacity)//构造函数
    {
        for (int i = 0; i < caches.Length; i++) {
            caches[i] = -1;//初始化为-1
        }
        _capacity = capacity;

        
        stack = new int[capacity];
        for (int i = 0; i < stack.Length; i++)
        {
            stack[i] = -1;//初始化为-1
        }
    }

    //void put(int key, int value) 
    //如果关键字 key 已经存在，则变更其数据值 value ；
    //如果不存在，则向缓存中插入该组 key-value 。
    //如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
    //问题：put算不算使用
    public void Put(int key,int value)
    {

        if (top == _capacity)//关键字数量超过 capacity
        {
            caches[stack[0]] = -1;//删除栈底的
            for (int i = 0; i < stack.Length-1; i++)
            {
                stack[i] = stack[i + 1];
            }
            top--;
        }


        if (caches[key]==-1)//不存在，则向缓存中插入该组 key-value 
        {
            stack[top++] = key;//key入栈

            caches[key] = value;//value入组
        }
        else//如果关键字 key 已经存在，则变更其数据值 value ；
        {

            caches[key] = value;//value入组
            //更新栈
            for(int i = 0;i < stack.Length;i++)
            {
                if (stack[i] == key)
                {
                    int temp= stack[i];//暂存一下，准备放到栈顶
                                       //后面的全部落下
                    for (int j = i; j < top-1; j++)
                    {
                        stack[j] = stack[j + 1]; 
                    }
                    stack[top - 1] = temp;//放到栈顶
                    break;
                }
               
            }
        }

       
    }
    //int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
    public int Get(int key)
    {
        for (int i = 0; i < stack.Length; i++)
        {
            if (stack[i] == key)
            {
                int temp = stack[i];//暂存一下，准备放到栈顶
                                    //后面的全部落下
                for (int j = i; j < top - 1; j++)
                {
                    stack[j] = stack[j + 1];
                }
                stack[top - 1] = temp;//放到栈顶
                break;
            }

        }



        return caches[key];


    }


}

public class DLinkedNode {

    public int key;
    public int value;
   public DLinkedNode next;
    public DLinkedNode prev;
    public DLinkedNode (int key=-1,int valve=-1){

        this.key = key;
        this.value = valve;
}

  
    }




public class LRUCache//使用双向链表+哈希表，双向链表有key和valve，哈希表key是key，val是listnode,
{
    int _capacity;
    Dictionary<int, DLinkedNode> HashMap;//val是listnode,为了方便更新栈
    DLinkedNode head = new DLinkedNode();
    


    public LRUCache(int capacity)//构造函数
    { 
        _capacity = capacity;

         HashMap = new Dictionary<int,DLinkedNode>();
        head.next = head;
        head.prev = head;
    }
    public void Put(int key, int value)
    {

        if (HashMap.ContainsKey(key))//key存在
        {
            DLinkedNode oldNode = HashMap[key];

            deleteFromList(oldNode);//删除旧节点

            DLinkedNode newNode = new DLinkedNode(key, value);
            HashMap[key] = newNode;//更新
            addToHead(newNode);

        }
        else//不存在，新增
        {
            if(HashMap.Count==_capacity)//满了
            {
                //Console.WriteLine("满了");
                //删除队尾
                HashMap.Remove(head.prev.key);//应该移除栈顶的hash
                deleteFromList(head.prev);
                
            }

            DLinkedNode newNode = new DLinkedNode(key, value);

            //新入栈的放到队头
            addToHead(newNode);
            HashMap.Add(key, newNode);
        }
       


    }
    //int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1
    public int Get(int key)
    {

       if( HashMap.TryGetValue(key, out DLinkedNode node))
        {
            //更新一下
            moveToHead(node);

            return node.value;
        }
        else
        {
            return -1;
        }

    }

    private void moveToHead(DLinkedNode node)
    {
       node.prev.next=node.next;
        node.next.prev = node.prev;
        node.next = head.next;

        node.next.prev = node;
        head.next = node;
        node.prev = head;
    }

    private void deleteFromList(DLinkedNode oldNode)
    {
        oldNode.prev.next=oldNode.next;
        oldNode.next.prev = oldNode.prev;
        oldNode = null;
    }

    public void addToHead(DLinkedNode newNode)
    {
        newNode.next = head.next;
        head.next = newNode;
        newNode.prev = head;
        newNode.next.prev = newNode;
    }

}

    class Program146
{

    static void Main146(string[] args)
    {
        LRUCache lRUCache = new LRUCache(2);//实例化一个类
        //int res = lRUCache.Get(0);    // 返回 -1 (未找到)
        //Console.WriteLine(res);
        lRUCache.Put(1, 1); // 缓存是 {1=1}

        lRUCache.Put(2, 2); // 缓存是 {1=1, 2=2}

        int res = lRUCache.Get(1);    // 返回 1

        Console.WriteLine(res);
        lRUCache.Put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
        res = lRUCache.Get(2);    // 返回 -1 (未找到)
        Console.WriteLine(res);
        lRUCache.Put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}

        res = lRUCache.Get(1);    // 返回 -1 (未找到)
        Console.WriteLine(res);
        res = lRUCache.Get(3);    // 返回 3
        Console.WriteLine(res);
        res = lRUCache.Get(4);    // 返回 4
        Console.WriteLine(res);
        //int[] ints = { 1, 2, 3 };
        //int[] ints = new int[10];//这个数组使用0初始化
        //Console.WriteLine(ints.Length);
        //Console.WriteLine(ints[0]);
        Console.ReadKey();
    }
}
